{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #完成一半题目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: halfQuestions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成一半题目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "有 `N` 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 `2*N` 道题目，整型数组 `questions` 中每个数字对应了每道题目所涉及的知识点类型。\r\n",
    "若每位扣友选择不同的一题，请返回被选的 `N` 道题目至少包含多少种知识点类型。\r\n",
    "\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`questions = [2,1,6,2]`\r\n",
    ">\r\n",
    ">输出：`1`\r\n",
    ">\r\n",
    ">解释：有 2 位扣友在 4 道题目中选择 2 题。\r\n",
    "> 可选择完成知识点类型为 2 的题目时，此时仅一种知识点类型\r\n",
    "> 因此至少包含 1 种知识点类型。\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`questions = [1,5,1,3,4,5,2,5,3,3,8,6]`\r\n",
    ">\r\n",
    ">输出：`2`\r\n",
    ">\r\n",
    ">解释：有 6 位扣友在 12 道题目中选择题目，需要选择 6 题。\r\n",
    "> 选择完成知识点类型为 3、5 的题目，因此至少包含 2 种知识点类型。\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "**提示：**\r\n",
    "- `questions.length == 2*n`\r\n",
    "- `2 <= questions.length <= 10^5`\r\n",
    "- `1 <= questions[i] <= 1000`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [WqXACV](https://leetcode.cn/problems/WqXACV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [WqXACV](https://leetcode.cn/problems/WqXACV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,6,2]', '[1,5,1,3,4,5,2,5,3,3,8,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import  Counter\n",
    "        n=int(len(questions)/2)\n",
    "        dic=Counter(tuple(questions))\n",
    "        lst=sorted(list(dic.values()),reverse=True)\n",
    "        \n",
    "        s=0\n",
    "        for i in range(n):\n",
    "            s+=lst[i]\n",
    "            if s>=n:\n",
    "                return i+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)/2\n",
    "        dic = {}\n",
    "        for i in questions:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        sc = sorted(dic.values(),reverse=True)\n",
    "\n",
    "        tc = 0\n",
    "        for c in sc:\n",
    "            n -= c \n",
    "            tc += 1\n",
    "            if n<=0:\n",
    "                break\n",
    "        return tc\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        size = len(questions)\n",
    "        people = size // 2\n",
    "        dic = [0] * 1000\n",
    "        for i in questions:\n",
    "            dic[i - 1] += 1\n",
    "        res = 0\n",
    "        while people > 0:\n",
    "            max_value = max(dic)\n",
    "            max_ind = dic.index(max_value)\n",
    "            people -= max_value\n",
    "            dic[max_ind] = 0\n",
    "            res += 1\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        m = {}\n",
    "        for q in questions:\n",
    "            if q not in m.keys():\n",
    "                m[q] = 1\n",
    "            else:\n",
    "                m[q] += 1\n",
    "        sm = sorted(m.items(), key=lambda row: row[1], reverse=True)\n",
    "        # print(\"sm=\", sm)\n",
    "        ans = 0\n",
    "        nums, total = 0, questions.__len__() // 2\n",
    "        for key, cnt in sm:\n",
    "            if nums >= total:\n",
    "                return ans\n",
    "            else:\n",
    "                ans += 1\n",
    "                nums += cnt\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        dic = collections.Counter(questions)\n",
    "        m = len(questions) // 2\n",
    "        count = 0\n",
    "        sum = 0\n",
    "        for val in sorted(list(dic.values()),reverse=True):\n",
    "            if sum >= m:\n",
    "                return count\n",
    "            else:\n",
    "                sum += val\n",
    "                count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        myd={}\n",
    "        for i in questions:\n",
    "            myd[i]=myd.get(i,0)+1\n",
    "        z=sorted([myd[i] for i in myd],reverse=True)\n",
    "        k=0\n",
    "        print(z)\n",
    "        while sum(z[:k])<len(questions)/2:\n",
    "            k+=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        peo = len(questions) / 2\n",
    "\n",
    "        dic = {}\n",
    "        for q in questions:\n",
    "            dic[q] = dic.get(q, 0) + 1\n",
    "        vals = list(dic.values())\n",
    "        vals.sort(reverse=True)\n",
    "        sp = 0\n",
    "        n = 0\n",
    "        for v in vals:\n",
    "            sp += v\n",
    "            n += 1\n",
    "            if sp >= peo:\n",
    "                return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)//2\n",
    "        a = sorted(collections.Counter(questions).items(), key= lambda x:x[1], reverse=True)\n",
    "        res = 1\n",
    "        freq = 0\n",
    "        for i in range(len(a)):\n",
    "            if freq + a[i][1] < n:\n",
    "                freq += a[i][1]\n",
    "                res += 1\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        q_freqs = {}\n",
    "        for q in questions:\n",
    "            if q not in q_freqs:\n",
    "                q_freqs[q] = 1\n",
    "            else:\n",
    "                q_freqs[q] += 1\n",
    "        freqs = list(q_freqs.values())\n",
    "        freqs.sort(reverse=True)\n",
    "        num_left = len(questions) // 2\n",
    "        num_types = 0\n",
    "        for f in freqs:\n",
    "            num_types += 1\n",
    "            num_left -= f\n",
    "            if num_left <= 0:\n",
    "                break\n",
    "        return num_types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)//2\n",
    "        ls = [item for item in Counter(questions).items()]\n",
    "        ls.sort(key = lambda x:(-x[1],x[0]))\n",
    "        ans = 0\n",
    "        for val,time in ls:\n",
    "            if time<n:\n",
    "                ans += 1\n",
    "                n -= time\n",
    "            else:\n",
    "                ans += 1\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        c = list(Counter(questions).values())\n",
    "        n = len(questions)//2\n",
    "        count = 0\n",
    "        while n>0:\n",
    "            n -= c.pop(c.index(max(c)))\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef halfQuestions(self, questions: List[int]) -> int:\n",
    "\t\tcounter = collections.Counter(questions)\n",
    "\t\tnum = len(questions) // 2\n",
    "\t\tcount = 0\n",
    "\t\tfor value in sorted(counter.values(), reverse=True):\n",
    "\t\t\tif num <= 0:\n",
    "\t\t\t\treturn count\n",
    "\t\t\telse:\n",
    "\t\t\t\tcount += 1\n",
    "\t\t\t\tnum -= value\n",
    "\t\tif num <= 0:\n",
    "\t\t\treturn count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)/2\n",
    "        dic = {}\n",
    "        for i in questions:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        sc = sorted(dic.values(),reverse=True)\n",
    "\n",
    "        tc = 0\n",
    "        for c in sc:\n",
    "            n -= c \n",
    "            tc += 1\n",
    "            if n<=0:\n",
    "                break\n",
    "        return tc\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 完成一半题目\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions) -> int:\n",
    "        n = len(questions)/2\n",
    "\n",
    "        type_map = Counter(questions).most_common()\n",
    "        \n",
    "        count = 0\n",
    "        for elem in type_map:\n",
    "            n -= elem[1]\n",
    "            count += 1\n",
    "            if n<=0:\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        a = Counter(questions)\n",
    "        b = dict(sorted(a.items(), key=lambda x: x[1], reverse=True))\n",
    "        conut = 0\n",
    "        n = len(questions)//2\n",
    "        for i, j in b.items():\n",
    "            if n > j:\n",
    "                n -= j\n",
    "                conut += 1\n",
    "            else:\n",
    "                break\n",
    "        conut += 1\n",
    "        return conut\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        people = len(questions) >> 1\n",
    "        cnt = sorted(Counter(questions).items(), key=lambda x: x[1], reverse=True)\n",
    "        ans = 0\n",
    "        for x, y in cnt:\n",
    "            if people > 0:\n",
    "                ans += 1\n",
    "                people -= y\n",
    "            else:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        fre = {}\n",
    "        for que in questions:\n",
    "            if que in fre:\n",
    "                fre[que] += 1\n",
    "            else:\n",
    "                fre[que] = 1\n",
    "        fre = sorted(fre.items(), key=lambda x: x[1], reverse=True)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        N = len(questions) // 2\n",
    "        for (k, v) in fre:\n",
    "            # print(k, \" \", v)\n",
    "            cnt += v\n",
    "            ans += 1\n",
    "            if cnt >= N:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        mp,f={},[]\n",
    "        for i in questions:mp[i]=mp.get(i,0)+1\n",
    "        for i in range(1,1001):\n",
    "            if(mp.get(i,0)):f.append(mp[i])\n",
    "        f.sort(reverse=True)\n",
    "        m,x,n=len(f),0,len(questions)//2\n",
    "        for i in range(m):\n",
    "            x+=f[i]\n",
    "            if(x>=n):return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        d = {}\n",
    "        for ele in questions:\n",
    "            if ele not in d:\n",
    "                d[ele] = 1\n",
    "            else:\n",
    "                d[ele] += 1\n",
    "        s = [d[ele] for ele in d]\n",
    "        s = sorted(s, reverse=True)\n",
    "        n = int(len(questions) // 2)\n",
    "        k = 0\n",
    "        for i in range(len(s)):\n",
    "            k += s[i]\n",
    "            if k >= n:\n",
    "                return i+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def halfQuestions(questions: list[int]) -> int:\n",
    "        unique_questions_list = list(set(questions))\n",
    "        unique_questions_list_with_counts = dict()\n",
    "\n",
    "        for idx, unique_question in enumerate(unique_questions_list):\n",
    "            count = 0\n",
    "            for question in questions:\n",
    "                if question == unique_question:\n",
    "                    count = count + 1\n",
    "\n",
    "            unique_questions_list_with_counts[idx] = count\n",
    "\n",
    "        count_list = unique_questions_list_with_counts.values()\n",
    "        sorted_count_list = sorted(count_list, reverse=True)\n",
    "\n",
    "        least_question_type = 1\n",
    "        question_select_quantity = len(questions) / 2\n",
    "\n",
    "        for count in sorted_count_list:\n",
    "            if question_select_quantity > count:\n",
    "                least_question_type = least_question_type + 1\n",
    "                question_select_quantity = question_select_quantity - count\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return least_question_type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 完成一半题目\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions) -> int:\n",
    "        n = len(questions)/2\n",
    "        values = sorted(Counter(questions).values(),reverse=True)\n",
    "\n",
    "        count = 0\n",
    "        for elem in values:\n",
    "            n -= elem\n",
    "            count += 1\n",
    "            if n<=0:\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        num = len(questions)/2\n",
    "        answer = [0 for i in range(1000)]\n",
    "        for question in questions:\n",
    "            answer[question-1] += 1\n",
    "        answer.sort(key=None, reverse=True)\n",
    "        \n",
    "        for type in range(1000):\n",
    "            num -= answer[type]\n",
    "            if num <= 0:\n",
    "                break\n",
    "        return type+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        nums = Counter(questions)\n",
    "        nums = sorted(nums.items(), key=lambda x: x[1], reverse=True)\n",
    "        cnt = 0\n",
    "        epo = 0\n",
    "        for item in nums:\n",
    "            cnt += item[1]\n",
    "            epo += 1\n",
    "            if cnt >= len(questions) / 2:\n",
    "                return epo\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)//2\n",
    "        counter = Counter(questions)\n",
    "        lst = list(counter.values())\n",
    "        lst.sort(key = lambda x: -x)\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while cnt < n:\n",
    "            cnt+=lst[i]\n",
    "            i+=1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        que_dict = collections.defaultdict(int)\n",
    "        for question in questions:\n",
    "            que_dict[question] += 1\n",
    "        cnt_list = list(que_dict.values())\n",
    "        cnt_list.sort(reverse=True)\n",
    "        ans = 0\n",
    "        n = len(questions) // 2\n",
    "        total = 0\n",
    "        while total < n:\n",
    "            total += cnt_list[ans]\n",
    "            ans += 1\n",
    "        return ans if cnt_list[0] < n else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 完成一半题目\n",
    "import collections\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions) -> int:\n",
    "        n = len(questions)/2\n",
    "\n",
    "        type_map = collections.Counter(questions).most_common()\n",
    "        \n",
    "        count = 0\n",
    "        for elem in type_map:\n",
    "            if n > 0:\n",
    "                n -= elem[1]\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        counter = collections.Counter(questions)\n",
    "        counter = sorted([(k, v) for k, v in counter.items()], key=lambda x: -x[1])\n",
    "        num_people = len(questions) / 2\n",
    "        \n",
    "        num_of_type = 0\n",
    "        num_of_q = 0\n",
    "        for _, num_of_q_of_curr_type in counter:\n",
    "            num_of_type += 1\n",
    "            num_of_q += num_of_q_of_curr_type\n",
    "            if num_of_q >= num_people:\n",
    "                return num_of_type\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        counter = Counter(questions)\n",
    "        nums = len(questions)/2\n",
    "        counter = dict(sorted(counter.items(),key = lambda x:x[1],reverse = True))\n",
    "        lis = list(counter.values())\n",
    "        res = 0\n",
    "        counts = 0\n",
    "        while counts < nums:\n",
    "            \n",
    "            counts += lis[res]\n",
    "            res +=1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[2,1,6,2]\n",
    "[1,5,1,3,4,5,2,5,3,3,8,6]\n",
    "\n",
    "questions.length == 2*n\n",
    "2 <= questions.length <= 10^5\n",
    "1 <= questions[i] <= 1000\n",
    "\n",
    "贪心,数组,哈希表,排序\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        N = len(questions)//2\n",
    "        freq = sorted(list(Counter(questions).values()))[::-1]\n",
    "        cnt = 1\n",
    "        for k in freq:\n",
    "            N -= k\n",
    "            if N <= 0:\n",
    "                return cnt\n",
    "            cnt += 1\n",
    "        raise 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)\n",
    "        cnt = Counter(questions)\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for v in sorted(cnt.values(), reverse=True):\n",
    "            s += v\n",
    "            ans += 1 \n",
    "            if s * 2 >= n:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 完成一半题目\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions) -> int:\n",
    "        n = len(questions)/2\n",
    "        type_map = {}\n",
    "        for elem in questions:\n",
    "            type_map[elem] = type_map.get(elem, 0) + 1\n",
    "        type_map = sorted(type_map.items(), key=lambda x: x[1], reverse=True)\n",
    "        \n",
    "        count = 0\n",
    "        for elem in type_map:\n",
    "            if n > 0:\n",
    "                n -= elem[1]\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = int(len(questions)/2)\n",
    "        tmp = Counter(questions)\n",
    "        for i,val in enumerate(sorted(tmp.values(), reverse=True)):\n",
    "            n -= val\n",
    "            if n<=0:\n",
    "                return i+1\n",
    "        return i+1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions) // 2\n",
    "        num_freq = sorted(collections.Counter(questions).items(), key = lambda x: x[1], reverse=True)\n",
    "        cnt = res = 0\n",
    "        for _, freq in num_freq:\n",
    "            if cnt < n: \n",
    "                cnt += freq\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        n = len(questions)//2\n",
    "        c = Counter(questions)\n",
    "        res = 0\n",
    "        ans = 0\n",
    "        for i in sorted(list(c.values()),reverse = True):\n",
    "            ans += 1\n",
    "            res += i\n",
    "            if res >= n:break\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        a = Counter(questions)\n",
    "        b = dict(sorted(a.items(), key=lambda x: x[1], reverse=True))\n",
    "        print(b)\n",
    "        conut = 0\n",
    "        n = len(questions)//2\n",
    "        for i, j in b.items():\n",
    "            if n > j:\n",
    "                n -= j\n",
    "                conut += 1\n",
    "            else:\n",
    "                break\n",
    "        conut += 1\n",
    "        return conut\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        ds,l = Counter(questions),len(questions)//2\n",
    "        vNs = sorted([x for x in ds.values()],reverse=True)\n",
    "        n = 0\n",
    "        for i,v in enumerate(vNs):\n",
    "            if n + v >= l:\n",
    "                return i + 1\n",
    "            else:\n",
    "                n += v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(questions) // 2\n",
    "        HashMap = dict()\n",
    "        for q in questions:\n",
    "            if q in HashMap:\n",
    "                HashMap[q] += 1\n",
    "            else:\n",
    "                HashMap[q] = 1\n",
    "        value = list(HashMap.values())\n",
    "        value.sort(reverse = True)\n",
    "        while n > 0:\n",
    "            n -= value[ans]\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        cnt = Counter(questions)\n",
    "        n = len(questions) // 2\n",
    "        sorted_items = sorted(cnt.items(), key=lambda x: x[1], reverse=True)\n",
    "\n",
    "        sum_count = 0\n",
    "        result = 0\n",
    "\n",
    "        for k, v in sorted_items:\n",
    "            sum_count += v\n",
    "            result += 1\n",
    "            if sum_count >= n:\n",
    "                break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        n=len(questions)//2\n",
    "        zd=Counter(questions)\n",
    "        list_=[]\n",
    "        for value in zd.values():\n",
    "            list_.append(value)\n",
    "        list_.sort()\n",
    "        list_.reverse()\n",
    "        m=len(list_)\n",
    "        sum_=0\n",
    "        for i in range(m):\n",
    "            sum_+=list_[i]\n",
    "            if sum_>=n:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions)//2\n",
    "        ls = [item for item in Counter(questions).items()]\n",
    "        ls.sort(key = lambda x:(-x[1],x[0]))\n",
    "        ans = 0\n",
    "        for val,time in ls:\n",
    "            if time<n:\n",
    "                ans += 1\n",
    "                n -= time\n",
    "            else:\n",
    "                ans += 1\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        cnt = sorted(Counter(questions).values(), reverse=True)\n",
    "        n = len(questions)//2\n",
    "        for i,c in enumerate(cnt):\n",
    "            n -= c\n",
    "            if n <= 0:\n",
    "                break\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        c = collections.Counter(questions)\n",
    "        t = 0\n",
    "        r = 0\n",
    "        n = len(questions) // 2\n",
    "        for v in sorted(c.values(), reverse=True):\n",
    "            r += 1\n",
    "            t += v\n",
    "            if t >= n:\n",
    "                return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        result = 0\n",
    "        selects = len(questions) // 2\n",
    "        d = {}\n",
    "        for i in questions:\n",
    "            if not i in d:\n",
    "                d[i] = 1\n",
    "            else:\n",
    "                d[i] += 1\n",
    "        ids = list(d.keys())\n",
    "        ids.sort(key = lambda a: d[a])\n",
    "        i = len(ids) - 1\n",
    "        count = 0\n",
    "        while i >= 0:\n",
    "            id = ids[i]\n",
    "            count += d[id]\n",
    "            result += 1\n",
    "            if count >= selects:\n",
    "                break\n",
    "            i -= 1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions) // 2\n",
    "        questions = collections.Counter(questions)\n",
    "        questions = sorted(questions.values(), reverse = True)\n",
    "        for i in range(len(questions)):\n",
    "            if questions[i] < n:\n",
    "                n -= questions[i]\n",
    "            else:\n",
    "                return i+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        Count=[0]*1000\n",
    "        for i in questions:\n",
    "            Count[i-1]+=1\n",
    "        Count.sort(reverse=True)\n",
    "        l=len(questions)//2\n",
    "        result=0\n",
    "        temp=0\n",
    "        print(Count)\n",
    "        for i in range(1000):\n",
    "            temp+=Count[i]\n",
    "            result+=1\n",
    "            if temp>=l:\n",
    "                return result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        ans, total, li = 0, 0, sorted(Counter(questions).values())\n",
    "        for index in range(1, len(questions)):\n",
    "            if total < len(questions) // 2:\n",
    "                total += li[-index]\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 完成一半题目\n",
    "import collections\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions) -> int:\n",
    "        n = len(questions)/2\n",
    "\n",
    "        type_map = collections.Counter(questions).most_common()\n",
    "        \n",
    "        count = 0\n",
    "        for elem in type_map:\n",
    "            if n > 0:\n",
    "                n -= elem[1]\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        num_P=len(questions)//2\n",
    "        Counter_i=Counter(questions).items()\n",
    "        num_freq = sorted(Counter_i, key = lambda x: x[1], reverse=True)\n",
    "        print(num_P)\n",
    "        print(num_freq)\n",
    "        res=0\n",
    "        count=0\n",
    "        for x, y in num_freq:\n",
    "            if count<num_P:\n",
    "                count+=y\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions) // 2\n",
    "        num_freq = sorted(collections.Counter(questions).items(), key = lambda x: x[1], reverse=True)\n",
    "        print(num_freq)\n",
    "        cnt = res = 0\n",
    "        for _, freq in num_freq:\n",
    "            if cnt < n: \n",
    "                cnt += freq\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        n=len(questions)//2\n",
    "        freqs=sorted(Counter(questions).items(),key=lambda x:x[1],reverse=True)\n",
    "\n",
    "        cnt=res=0\n",
    "        for i,freq in freqs:\n",
    "            if cnt<n:\n",
    "                cnt+=freq\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n=len(questions)//2\n",
    "        aa=[j for i,j in Counter(questions).items()]\n",
    "        aa.sort(reverse=True)\n",
    "        count=0\n",
    "        for i in aa:\n",
    "            n-=i \n",
    "            count+=1\n",
    "            if n<=0:\n",
    "                break\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        dict_type = Counter(questions)\n",
    "        nums = len(questions) // 2\n",
    "        q_list = sorted(dict_type,key=lambda x:-dict_type[x])\n",
    "        sum = 0\n",
    "        for i,v in enumerate(q_list):\n",
    "            sum+=dict_type[v]\n",
    "            if sum>=nums:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions) // 2\n",
    "        num_freq = sorted(collections.Counter(questions).items(), key = lambda x: x[1], reverse=True)\n",
    "        cnt = res = 0\n",
    "        for _, freq in num_freq:\n",
    "            if cnt < n: \n",
    "                cnt += freq\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions) // 2\n",
    "        num_freq = sorted(collections.Counter(questions).items(), key = lambda x: x[1], reverse=True)\n",
    "        cnt = res = 0\n",
    "        for _, freq in num_freq:\n",
    "            if cnt < n: \n",
    "                cnt += freq\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        n = len(questions) // 2\n",
    "        num_freq = sorted(collections.Counter(questions).items(), key = lambda x: x[1], reverse=True)\n",
    "        cnt = res = 0\n",
    "        for _, freq in num_freq:\n",
    "            if cnt < n: \n",
    "                cnt += freq\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfQuestions(self, questions: List[int]) -> int:\n",
    "        hashmap = {}\n",
    "        for q in questions:\n",
    "            if q not in hashmap:\n",
    "                hashmap[q] = 0\n",
    "            hashmap[q] += 1\n",
    "\n",
    "        ans = 0\n",
    "        k = 0\n",
    "        length = len(questions) / 2\n",
    "        for q, n in sorted(hashmap.items(), key=lambda x: -x[-1]):\n",
    "            if k >= length:\n",
    "                break\n",
    "            k += n\n",
    "            ans += 1\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
